Algorithms for the weight constrained shortest path problem

Title: Algorithms for the weight constrained shortest path problem
Creator: Dumitrescu, Irina; Boland, Natashia
Relation: International Transactions in Operations Research Vol. 8, Issue 1, p. 15-29
Publisher Link: http://dx.doi.org/10.1111/1475-3995.00003
Publisher: Wiley-Blackwell Publishing
Resource Type: journal article
Date: 2001
Description: Given a directed graph whose arcs have an associated cost, and associated weight, the weight constrained shortest path problem (WCSPP) consists of finding a least-cost path between two specified nodes, such that the total weight along the path is less than a specified value. We will consider the case of the WCSPP defined on a graph without cycles. Even in this case, the problem is NP-hard, unless all weights are equal or all costs are equal, however pseudopolynomial time algorithms are known. The WCSPP applies to a number of real-world problems. Traditionally, dynamic programming approaches were most commonly used, but in recent times other methods have been developed, including exact approaches based on Lagrangean relaxation, and fully polynomial approximation schemes. We will review the area and present a new exact algorithm, based on scaling and rounding of weights.
Subject: combinatorial optimization; networks; routing
Identifier: http://hdl.handle.net/1959.13/939506
Identifier: uon:12825
Identifier: ISSN:0969-6016
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format